题目背景
AC_Automation 作为一个可爱的妹子,她喜欢求和与乘积,还特别喜欢长的东西。现在她给你一个很长的序列,想让你求一些东西。看在她那么可爱的份上,就帮帮她吧。
题目描述
她本来想给你一个很长的序列 ,但是为了让你解出题目,善良的她给了一个较短的序列 来表示所有在序列 的中的数。具体来讲,序列 和序列 之间的关系为:
(其中 )
可以发现,序列 的下标在 之间。她还定义了一个函数 ,满足:
现在她给了你一个长度为 的序列 ,以及 个询问,对于第 个询问 ,请你求出对应的 。因为她很讨厌高精度,为了满足她的要求,请你输出该值模上 的值
由于她太菜了,看在她那么可爱的份上,就帮帮她吧。
输入格式
第一行两个整数 和 ,分别表示序列长度和询问的个数
第二行 个正整数 ,表示 AC_Automation 给你的一个序列。
接下来 行,每行一个 和 ,表示 个询问。
输出格式
行,表示每个 和 所对应的 模上 的值
样例输入
2 3
1 2
1 8
1 16
9 16
样例输出
30
72
42
样例解释
数据范围与约定
| 测试点序号 | ||
|---|---|---|
对于 的数据,,,,。
题解
没有前缀和的暴力,得 分,有前缀和的暴力,得 分。
我们来考虑如何得到这 分。
可以发现,由于 ,所以我们可以写一个 的算法。具体来讲,我们可以令一个二维数组 ,其中 。那么
我们来看这个式子(其中假设 , ,且 ):
具体来讲,每个 所对应的 和 如下图:
假如 ,我们就可以有这样的变换:
我们令 (可以发现这是可以预处理的),那么
结构如下图:
同样,在 的时候,也有这样的变换:
结构如下图:
既然这样,那么我们就可以得到做法了:先看 之间有几个 长度的块,将其求和,再将一些零碎的东西再求和。
好了,这 分的思路都有了, 分的思路也不难了吧(也就是把这个长度为 的序列分别分成长度为 、 、 的块,分得细一些,稍稍麻烦一些)。这是我丑陋的代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 1e9 + 7.5;
const int N = 10005;
LL B[N], PreSum[N];
int n, T;
inline LL f(LL l, LL r) {
LL ret = 0ll;
LL tl = 0, tr = 0;
tl = (l - 1) / ((LL)(n * n) * (LL)n) + 2;
tr = (r - 1) / ((LL)(n * n) * (LL)n);
if (tl <= tr) {
(ret += (((PreSum[tr] - PreSum[tl - 1]) * PreSum[n]) % mod) * ((n * n) % mod)) %= mod;
(ret += ((PreSum[n] * PreSum[n]) % mod) * (((tr - tl + 1) * n) % mod)) %= mod;
}
tl--; tr++;
if (tl != tr) {
LL ttl = (l - 1) / (LL)(n * n) + 2, ttr = tl * n;
if (ttl <= ttr)
(ret += ((B[tl] * (PreSum[(ttr - 1) % n + 1] - PreSum[(ttl - 1) % n])) % mod) * (n * n)) %= mod,
(ret += ((PreSum[n] * PreSum[n]) % mod) * (ttr - ttl + 1)) %= mod;
ttl = (tr - 1) * n + 1, ttr = (r - 1) / (LL)(n * n);
if (ttl <= ttr)
(ret += ((B[tr] * (PreSum[(ttr - 1) % n + 1] - PreSum[(ttl - 1) % n])) % mod) * (n * n)) %= mod,
(ret += ((PreSum[n] * PreSum[n]) % mod) * (ttr - ttl + 1)) %= mod;
} else {
LL ttl = (l - 1) / (LL)(n * n) + 2, ttr = (r - 1) / (LL)(n * n);
if (ttl <= ttr)
(ret += ((B[tl] * (PreSum[(ttr - 1) % n + 1] - PreSum[(ttl - 1) % n])) % mod) * (n * n)) %= mod,
(ret += ((PreSum[n] * PreSum[n]) % mod) * (ttr - ttl + 1)) %= mod;
}
LL ttl = (l - 1) / (LL)(n * n) + 1, ttr = (r - 1) / (LL)(n * n) + 1;
if (ttl != ttr) {
LL tttl = (l - 1) / n + 2, tttr = ttl * n;
if (tttl <= tttr)
(ret += ((B[tl] * B[(ttl - 1) % n + 1]) % mod) * (tttr - tttl + 1) * n) %= mod,
(ret += (PreSum[(tttr - 1) % n + 1] - PreSum[(tttl - 1) % n]) * PreSum[n]) %= mod;
tttl = (ttr - 1) * n + 1, tttr = (r - 1) / n;
if (tttl <= tttr)
(ret += ((B[tr] * B[(ttr - 1) % n + 1]) % mod) * (tttr - tttl + 1) * n) %= mod,
(ret += (PreSum[(tttr - 1) % n + 1] - PreSum[(tttl - 1) % n]) * PreSum[n]) %= mod;
} else {
LL tttl = (l - 1) / n + 2, tttr = (r - 1) / n;
if (tttl <= tttr)
(ret += ((B[tl] * B[(ttl - 1) % n + 1]) % mod) * (tttr - tttl + 1) * n) %= mod,
(ret += (PreSum[(tttr - 1) % n + 1] - PreSum[(tttl - 1) % n]) * PreSum[n]) %= mod;
}
LL tttl = (l - 1) / (LL)n + 1, tttr = (r - 1) / (LL)n + 1;
if (tttl != tttr) {
LL ttttl = l, ttttr = tttl * n;
(ret += ((B[tl] * B[(ttl - 1) % n + 1]) % mod) * (ttttr - ttttl + 1)) %= mod;
(ret += B[(tttl - 1) % n + 1] * (PreSum[(ttttr - 1) % n + 1] - PreSum[(ttttl - 1) % n])) %= mod;
ttttl = (tttr - 1) * n + 1, ttttr = r;
(ret += ((B[tr] * B[(ttr - 1) % n + 1]) % mod) * (ttttr - ttttl + 1)) %= mod;
(ret += B[(tttr - 1) % n + 1] * (PreSum[(ttttr - 1) % n + 1] - PreSum[(ttttl - 1) % n])) %= mod;
} else {
LL ttttl = l, ttttr = r;
(ret += ((B[tl] * B[(ttl - 1) % n + 1]) % mod) * (ttttr - ttttl + 1)) %= mod;
(ret += B[(tttl - 1) % n + 1] * (PreSum[(ttttr - 1) % n + 1] - PreSum[(ttttl - 1) % n])) %= mod;
}
return (ret + mod) % mod;
}
int main() {
scanf("%d%d", &n, &T);
for (int i = 1; i <= n; i++) scanf("%lld", B + i), PreSum[i] = (PreSum[i - 1] + B[i]) % mod;
for (LL l, r; T--; ) {
scanf("%lld%lld", &l, &r);
if (l > r || l < 1 || l > (LL)n * (LL)n * (LL)n * (LL)n || r < 1 || r > (LL)n * (LL)n * (LL)n * (LL)n) throw 112;
printf("%lld\n", f(l, r));
}
return 0;
}
感谢阅读!